Entropy coding is the process of representing data with the smallest average number of bits, and thus is a fundamental technique on all media compression methods. Arithmetic coding is an entropy coding method that has higher computational complexity than other coding techniques like prefix-coding (e.g., Huffman, Rice, exp-Golomb codes), but since it yields better compression, it has been adopted as the unique entropy coding method in the recent video coding standards H.265/HEVC and VP9, and thus is expected to be the sole entropy coding method of future standards.
However, in a video coding standard, a bit syntax of mapped to pseudo-random selection of finite-state-machines (FSM), which removes a possibility of parallel implementations regarding increasing throughput, is defined to severely limit data throughput of video encoding/decoding.
Thus, in order to allow for extended parallelization, a segmented bit format is required to be defined, and here, a data segment is defined by an independent entropy coding FSM that may be processed in parallel at an end portion of a coding process or at a start portion of decoding. This approach, however, may be appropriate for execution of software in a general processor because thread management or communication overheads may be avoided, but may not be optimal for general hardware in which overhead is not significant and processed elements are required to be temporarily in an idle state.